/*-------------------------------------------------------------------------
 *
 * checksum_impl.h
 *	  数据页面的校验和实现.
 *
 * 此文件的存在是为了让外部程序可以检查
 * Postgres 页面校验和. 它们可以 #include 这个文件以获取
 * storage/checksum.h 中引用的代码. (注意: 你可能需要重新定义
 * Assert() 为空以便外部成功编译.)
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/include/storage/checksum_impl.h
 *
 *-------------------------------------------------------------------------
 */


/*
 * 用于校验和页面的算法选择了非常快速的计算方式。
 * 对于数据库工作集适合放入操作系统文件缓存但不
 * 适合放入共享缓冲区的工作负载，可以以非常快的速度读取页面，
 * 而校验和算法本身可能成为最大瓶颈。
 *
 * 校验和算法本身基于FNV-1a哈希（FNV是Fowler/Noll/Vo的简称）。
 * 普通FNV-1a哈希的基本操作是根据以下公式逐字节折叠数据：
 *
 *	   hash = (hash ^ value) * FNV_PRIME
 *
 * FNV-1a算法的描述请参见http://www.isthe.com/chongo/tech/comp/fnv/
 *
 * PostgreSQL并不直接使用FNV-1a哈希，因为它在高位混合上表现不好 -
 * 输入数据的高阶位仅影响输出数据的高阶位。为了解决这个问题，
 * 我们在乘法之前将值与之进行异或，并向右移动17位。选择17这个数字是因为
 * 它与FNV_PRIME中的设置位位置没有共同的约数，并且根据经验能快速
 * 使最终迭代的高阶位均匀分布到较低位置。出于性能原因，我们选择每次
 * 结合4个字节。实际使用的哈希公式为：
 *
 *	   hash = (hash ^ value) * FNV_PRIME ^ ((hash ^ value) >> 17)
 *
 * 这个计算的主要瓶颈是乘法延迟。为了解决延迟并利用SIMD并行性，
 * 多个哈希值同时计算。页面被视为一个32列的32位值的二维数组。
 * 每一列分别聚合成一个部分校验和。每个部分校验和使用不同的初始
 * 值（在FNV术语中的偏移基数）。实际使用的初始值是随机选择的，因为
 * 值本身并没有那么重要，重要的是它们不同并且与真实数据不匹配。
 * 在初始化部分校验和后，根据上述公式对列中的每个值进行聚合。
 * 最后再进行两次值为0的公式迭代，以混合最后添加的值的位。
 *
 * 然后通过异或将部分校验和折叠在一起，形成单个32位校验和。调用者
 * 可以安全地通过模2^16-1将值减少到16位。这会造成轻微的偏差
 * 向较低的值，但这对校验和的性能并不显著。
 *
 * 算法选择基于SIMD指令集中的可用指令。这意味着一个快速且良好的
 * 算法需要使用乘法作为主要混合操作符。最简单基于乘法的校验和基本
 * 操作是FNV所使用的。选择的质数是为了良好的值扩散。它没有已知的
 * 简单模式会导致碰撞。对64位键的基本操作的5位差分测试
 * 显示在100000个随机键中没有3个或更多值发生碰撞。雪崩测试表明
 * 只有最后一个字的高阶位存在偏差。对1-4个不相关的位错误、零值和
 * 0xFF字节的测试，随机位置到结束用0字节覆盖页面，以及用0x00、0xFF
 * 和随机数据覆盖页面的随机段的测试都显示，在误差范围内存在最优
 * 的2e-16假阳性率。
 *
 * 算法的向量化需要32位x32位->32位整数乘法指令。到2013年，相关的
 * 指令在x86 SSE4.1扩展（pmulld）和ARM NEON（vmul.i32）中均可用。
 * 向量化需要编译器为我们进行向量化。对于最新的GCC版本，-msse4.1
 * -funroll-loops -ftree-vectorize标记就足够实现向量化。
 *
 * 使用的最佳并行度取决于CPU特定指令延迟、SIMD指令宽度、吞吐量
 * 和可用来保存中间状态的寄存器数量。通常，更高的并行性更好，直到
 * 状态无法放入寄存器，并且需要额外的加载-存储指令来交换值进出。
 * 选择的数字是算法的一部分，因为更改并行度会改变校验和结果。
 *
 * 并行数32的选择是基于它是可在架构上可见的x86 SSE寄存器中适合
 * 的最大状态，同时为中间值留出一些空寄存器。对于未来具有256位
 * 向量寄存器的处理器，这将会留下些许性能损失。当向量化不可用时，
 * 重构计算以一次计算一部分列并进行多次遍历以避免寄存器溢出
 * 可能是有益的。这一优化机会没有被使用。当前的编码也假设编译器
 * 能够展开内循环以避免循环开销并最小化寄存器溢出。对于不太复杂
 * 的编译器，手动展开内循环可能是有益的。
 */

#include "storage/bufpage.h"

/* 计算并行校验和的数量 */
#define N_SUMS 32
/* FNV-1a 哈希的素数乘数 */
#define FNV_PRIME 16777619

/* 使用联合体，以确保在严格别名下代码有效 */
typedef union
{
	PageHeaderData phdr;
	uint32		data[BLCKSZ / (sizeof(uint32) * N_SUMS)][N_SUMS];
} PGChecksummablePage;

/*
 * 基础偏移量以初始化每个并行 FNV 哈希为
 * 不同的初始状态。
 */
static const uint32 checksumBaseOffsets[N_SUMS] = {
	0x5B1F36E9, 0xB8525960, 0x02AB50AA, 0x1DE66D2A,
	0x79FF467A, 0x9BB9F8A3, 0x217E7CD2, 0x83E13D2C,
	0xF8D4474F, 0xE39EB970, 0x42C6AE16, 0x993216FA,
	0x7B093B5D, 0x98DAFF3C, 0xF718902A, 0x0B1C9CDB,
	0xE58F764B, 0x187636BC, 0x5D7B3BB1, 0xE73DE7DE,
	0x92BEC979, 0xCCA6C0B2, 0x304A0979, 0x85AA43D4,
	0x783125BB, 0x6CA8EAA2, 0xE407EAC6, 0x4B5CFC3E,
	0x9FBF8C76, 0x15CA20BE, 0xF2CA9FD3, 0x959BD756
};

/*
 * 计算一轮校验和。
 */
#define CHECKSUM_COMP(checksum, value) \
do { \
	uint32 __tmp = (checksum) ^ (value); \
	(checksum) = __tmp * FNV_PRIME ^ (__tmp >> 17); \
} while (0)

/*
 * 块校验和算法。页面必须适当对齐
 * （至少在4字节边界上）。
 */
static uint32
pg_checksum_block(const PGChecksummablePage *page)
{
	uint32		sums[N_SUMS];
	uint32		result = 0;
	uint32		i,
				j;

	/* 确保大小与算法兼容 */
	Assert(sizeof(PGChecksummablePage) == BLCKSZ);

	/* 将部分校验和初始化为对应的偏移量 */
	memcpy(sums, checksumBaseOffsets, sizeof(checksumBaseOffsets));

	/* 主校验和计算 */
	for (i = 0; i < (uint32) (BLCKSZ / (sizeof(uint32) * N_SUMS)); i++)
		for (j = 0; j < N_SUMS; j++)
			CHECKSUM_COMP(sums[j], page->data[i][j]);

	/* 最后添加两轮零以进行额外的混合 */
	for (i = 0; i < 2; i++)
		for (j = 0; j < N_SUMS; j++)
			CHECKSUM_COMP(sums[j], 0);

	/* 将部分校验和进行异或折叠 */
	for (i = 0; i < N_SUMS; i++)
		result ^= sums[i];

	return result;
}

/*
 * 计算 Postgres 页面校验和。
 *
 * 页面必须适当对齐（至少在 4 字节边界上）。
 * 还要注意，页面的校验和字段是暂时置为零的。
 *
 * 校验和包括块号（以检测页面被
 * 以某种方式移动到不同位置的情况）、页面头（不包括
 * 校验和本身）和页面数据。
 */
uint16
pg_checksum_page(char *page, BlockNumber blkno)
{
	PGChecksummablePage *cpage = (PGChecksummablePage *) page;
	uint16		save_checksum;
	uint32		checksum;

	/* 我们只计算正确初始化的页面的校验和 */
	Assert(!PageIsNew(&cpage->phdr));

	/*
	 * 保存 pd_checksum，并暂时将其设置为零，以便校验和
	 * 计算不受页面上存储的旧校验和的影响。
	 * 之后恢复它，因为实际更新校验和并不是
	 * 该函数的 API 一部分。
	 */
	save_checksum = cpage->phdr.pd_checksum;
	cpage->phdr.pd_checksum = 0;
	checksum = pg_checksum_block(cpage);
	cpage->phdr.pd_checksum = save_checksum;

	/* 混合块号以检测转置页面 */
	checksum ^= blkno;

	/*
	 * 减少为 uint16（以适应 pd_checksum 字段），并偏移
	 * 一个。这避免了零的校验和，这似乎是个好主意。
	 */
	return (uint16) ((checksum % 65535) + 1);
}
